package everydayone.gameOfLife;
/**
 * @Date 2020/04/02
 * @author 王光浩
 * @Thinking 使用原地算法。当使用这种算法时我们不能直接修改元素值为0 或1，所以我们需要借助一些中间变量
 * @         这些中间变量既要标识元素的原始状态，又标识这元素未来的变化。细胞的状态转化：死->活；活->死
 * @         维持原状态。设置：-1为死细胞将变活；设置2为活细胞将变死。
 * @Analysis 时间复杂度O（n*m），空间复杂度O（1）
 */
public class MyMethodTwo {
	public void gameOfLife(int[][] board) {
		for(int i=0;i<board.length;i++) {
			for(int j=0;j<board[0].length;j++) {
				int alive=helper(board,i,j);
				if(board[i][j]==1) {
					if(alive<2 || alive>3)board[i][j]=2;  //活细胞将变死
				}
				else if(alive==3)board[i][j]=-1;  //标志死细胞将变活
			}
		}
		for(int i=0;i<board.length;i++)
			for(int j=0;j<board[0].length;j++) {
				if(board[i][j]==2)board[i][j]=0;
				else if(board[i][j]==-1)board[i][j]=1;
			}
    }
	private int helper(int[][] board,int x,int y) {
		int[] indexX= {-1,1,0,0,-1,-1,1,1,}; //上下左右，左上，右上，右下，左下
		int[] indexY= {0,0,-1,1,-1,1,1,-1};
		int count=0;  //统计存活细胞的数目
		for(int i=0;i<8;i++) {
			int currentX=x+indexX[i];
			int currentY=y+indexY[i];
			if( (currentX>=0 && currentX<board.length) && (currentY>=0 && currentY<board[0].length)) {
				if(board[currentX][currentY]>=1)count++;
			}
		}
		return count;
	}
}
